package listbyorder.access101_200.test117;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/8 9:31
 */
public class Solution1 {

    // 太帅了
    public Node connect(Node root) {
        if (root == null) return null;
        // 定义两个指针
        Node pre = root;   // pre指向的是该行的头节点
        Node cur = null;
        while (true) {
            cur = pre;
            while (cur != null) {
                // 如果当前cur节点的左右孩子都是null，则直接next到下一个节点求解即可
                if (cur.left == null && cur.right == null) {
                    cur = cur.next;
                    continue;
                }
                // 至少有一个节点不为null
                Node next = cur.next;
                while (next != null && next.left == null && next.right == null) {
                    next = next.next;
                }
                // 如果当前cur节点的左右孩子都存在
                if (cur.left != null && cur.right != null) {
                    cur.left.next = cur.right;
                }
                // 如果next不为null，则可能有子节点，为null不考虑
                if (next != null) {
                    Node temp = cur.right == null ? cur.left : cur.right;
                    if (next.left != null) {
                        temp.next = next.left;
                    } else {
                        temp.next = next.right;
                    }
                }
                // 当前cur走完了
                cur = cur.next;
            }
            // 走出cur ！= null 循环，出来表示当前层已经走完了
            while (pre.left == null && pre.right == null) {
                pre = pre.next;
                // 三个指针都为null，已经遍历到了最后
                if (pre == null) {
                    return root;
                }
            }
            // 进入下一层
            pre = pre.left == null ? pre.right : pre.left;
        }
    }
}
